package primary.code08;

import lombok.extern.slf4j.Slf4j;

import java.util.LinkedList;

/**
 * 滑动窗口最大值问题
 * <p>
 * 问题：
 * <p>
 * 长度为length的数字数组，长度为 w 的滑动窗口，求解滑动窗口在所有位置上的最大值
 * <p>
 * 分析：
 * <p>
 * 使用双端队列结构，始终保持严格的从大->小的队列结构，队头即为当前窗口内的最大值.
 * R向右移动，窗口内元素增加，弹出“值小于等于新元素”后，将新元素添加至队列尾部.
 * L向右移动，窗口内元素减少，减少的元素如果是队头元素，则将队头元素移除.
 */
@Slf4j
public class Code06_SlidWindow {

    public static int[] slidWindowMaxNum(int[] arr, int w) {
        if (arr == null || arr.length < w || w <= 0) {
            return null;
        }
        int[] res = new int[arr.length - w + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int r = 0; r < arr.length; r++) {
            while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[r]) {
                queue.removeLast();
            }
            queue.addLast(r);
            int left = r - w + 1;
            if (left >= 0) {
                res[left] = arr[queue.peekFirst()];
                if ((left - 1) == queue.peekFirst()) {
                    queue.removeFirst();
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] ints = slidWindowMaxNum(new int[]{5, 3, 6, 1, 5, 7, 8, 3}, 3);
        for (int anInt : ints) {
            // 6-6-6-7-8-8-
            System.out.print(anInt + "-");
        }
    }
}
